1. Field of the Invention
The present invention relates a broadcast encryption method, and more particularly, to a broadcast encryption method being secure against collusion attacks.
2. Description of the Related Art
In general, the encryption systems are classified into a symmetric key (also referred to as a secret key) encryption system and an asymmetric key (also referred to as a public key) encryption system.
The symmetric key encryption system uses the same key for encryption and decryption. For example, if a sender converts an original message into an encrypted message through an encryption key and an encryption algorithm and sends the encrypted message to a receiver, the receiver converts the encrypted message into the original message by applying the same key to a decryption algorithm.
The receiver has to exchange keys safely prior to the encrypted communications, and a third party who attempts to view the encrypted communications can not view the original message without the keys that the sender and receiver have used. However, problems on key management and exchanges can occur since the number of keys to be managed accordingly increases if encrypted messages are to be sent to more parties.
Compared to the symmetric key encryption system, the asymmetric key encryption system is based on mathematical functions, in which there exists a pair of keys, wherein one of the keys is open to anyone else for its use, and the other key is kept secret. In here, the open key is referred to as a public key, and the secretly-kept key is referred to as a private key.
In order for a sender and a receiver to perform encryption communications by using the public key, the sender first encrypts an original message by using a public key of the receiver to send the encrypted message to the receiver, and the receiver decrypts the encrypted message by using a private key of his own to obtain the original message. Even though someone gets an encrypted message on a network, data can be safely sent since the encrypted message can not be decrypted without the private key which is kept by its owner all the time and has no need to be open or sent to others.
On the other hand, the symmetric key (or cipher) is mainly used to encrypt or decrypt broadcast streams, because the encryption and decryption can be carried out very rapidly when the symmetric key is used and the symmetric key can be safely sent through a limited access system to which only authenticated are accessible.
Contents creators create various useful data such as audio and video data in a data transmission system based on general broadcast encryptions, and provide the created data with service providers. The service providers broadcast the data of the contents creators through various wire and wireless communication networks to authorized users such as smart home Digital Rights management (DRM) networks and mobile DRM networks.
FIG. 1 is a view for showing a general broadcast transmission system. In FIG. 1, a service provider 100 produces a broadcast message 110 and sends the broadcast message 110 to users through various transmission channels 120. In here, the broadcast message 110 is sent to privileged users 130 as well as to revoked users. Thus, the service provider 100 allocates a separate key to encrypt the broadcast message 110 in order for the privileged users 130 to read the sent broadcast message 110. Therefore, an important issue in the broadcast system is the method of producing a certain group key in order for only the privileged users 130 to decrypt the encrypted broadcast message.
For example, the service provider 100 can send data through satellites to users devices such as set-top boxes coming with various satellite receivers, as well as send the data to mobile communication terminals through mobile communication networks. Further, the service provider 100 can send the data to various terminals on a smart home network through the Internet.
On the other hand, the service provider 100 encrypts the data by using broadcast encryption (BE) to prevent unauthorized users from using the data.
The security in such an encryption/decryption system mainly depends on a system for managing encryption keys. Further, methods for deriving keys is most important in such an encryption key management system. In addition, it is important to manage and update the derived encryption keys.
On the other hand, the data transmission method by using the public key is a method for sending data including key values of authorized users when data is sent. That is, data sent by the service provider 100 through broadcast/home networks contains a header portion having authentication information and an encrypted data portion having substantial data information.
Thus, the header portion contains a group identifier (ID) and key value information of authenticated users included in each authorized group so that, of plural users, data can be sent to only the users of the authorized groups.
Therefore, if data is encrypted and sent through a certificate revocation list/online certificate status protocol (CRL/OCSP) including a CRL and OCSP information, users receiving the data check their own key value information included in the header portion of the data, get authenticated in due course, and use their desired data.
On the other hand, the header portion in the broadcast encryption (BE) scheme contains only information of a group ID and a key value for a certain group. Thus, the privileged users of authenticated groups can use their own group key values in order to decrypt the received data into original data.
There exist methods disclosed in the “Broadcast Encryption” (Fiat et al., Crypto '93 LINCS vol. 839, pp 480-491, which is, hereinafter, referred to as the “Fiat algorithm”) as the other methods for broadcasting encryption keys. The ‘Fiat algorithm’ proposes two basic broadcast encryption algorithms and an algorithm having higher security against collusion attacks.
Hereinafter, a brief description will provided for the Fiat algorithm. Coefficients are first defined as below for the description of the Fiat algorithm.                U: Set of users with |U|=n        P: Set of privileged users with |U−P|=r        N: RSA composite        y1, . . . , yn: Distinct primes        usri: An user in U where 1≦i≦n        O: A positive integer satisfying 1<0<N        
The Fiat algorithm enables a server to produce system coefficients N, y1, . . . , yn, and O, of the defined coefficients, in the system initialization step, and discloses the coefficients N, y1, . . . , yn, of the system coefficients, in order for anyone to look them up. Further, if a user usri subscribes to services, the server carries out tasks as below:
1. assign a value yi to a user usri 
2. calculate secret information, ui═Oyi(mod N), of the user usri 
3. send the calculated secret information safely to the user usri 
The initialization and user subscription steps are completed through the above tasks. Now, if given a group of privileged users, P⊂U, a group key Kp for each user is expressed in Equation 1 as follows:
                              K          p                =                              O                                          ∏                                                      usr                    s                                    ∈                  P                                            ⁢                                                          ⁢              ys                                ⁡                      (                          mod              ⁢                                                          ⁢              N                        )                                              [                  Equation          ⁢                                          ⁢          1                ]            
Users included in P can use the value ui assigned from the server to calculate the group key Kp of Equation 1 by using Equation 2 as follows:
                              K          p                =                                            u              i                                                      ∏                                                      usr                    s                                    ∈                                      P                    -                                          (                                              usr                        i                                            )                                                                                  ⁢                                                          ⁢              ys                                ⁡                      (                          mod              ⁢                                                          ⁢              N                        )                                              [                  Equation          ⁢                                          ⁢          2                ]            
Unauthorized subscribers or revocaters who are not normal subscribers have, in the exponent part ui, the distinct prime yi not included in the exponent part of Kp, so the group key Kp can be calculated when the distinct prime yi is eliminated from the exponent part.
However, the calculation is practically impossible due to a problem of ‘difficult prime factorization of N’. Thus, the broadcast encryption becomes possible for privileged users through the above method.
However, the above Fiat algorithm causes a serious security problem when two users, for example, usr1 and usr2, share the secret information each other. That is, since yi and yj are primes to each other, integers a and b satisfying ayi+byj=1 can be easily obtained. Therefore, the two users can obtain a value of O being the secret system information by using Equation 3 as below:uiaujb≡Oayi+byj=O(mod N)  [Equation 3]
Thus, the unauthorized users can obtain the group key Kp in all circumstances by using the value of O. That is, if two malicious users collude with each other, the two basic algorithms cause the system to be insecure any further since the secret information of a server broadcasting contents is oozed out.
As above, systems referred to as “1-resilient systems” are ones secure against one aggressive operator but not secure against two aggressive operators. On the other hand, the Fiat algorithm proposes a k-resilient system based on the 1-resilient system, but has a problem of high inefficiency.
The k-resilient system is that receivers (t receivers at maximum) eliminate an arbitrary number of receivers colluding with one another. However, the method needs a relatively long message, a relatively many keys stored in a receiver, and more-than-once decryption operations by each receiver.
Further, the method does not take a stateless receiver scenario into consideration. There needs to avoid an assumption on how many receivers collude with one another. Further, the message size and the number of stored keys need to be minimized, and the decryption operations to be carried out by a receiver have to be minimized for optimal performance.
On the other hand, the other systems like the Fiat system do not provide the stateless receiver scenario, so that the other systems can not be effectively applied to the protection of contents on recording media.